10801 - Lift hopping/10801.cpp

   1 #include <sstream>
   2 #include <queue>
   3 #include <iostream>
   4 #include <vector>
   5
   6 using namespace std;
   7
   8 struct edge{
   9   int to, weight, lift;
  10   edge(int t, int w, int l) : to(t), weight(w), lift(l) {}
  11   bool operator < (const edge &that) const{
  12     return weight > that.weight;
  13   }
  14 };
  15
  16 int main(){
  17   int n, k;
  18   while (cin >> n >> k){
  19     vector<edge> g[100];
  20     int t[n];
  21     for (int i=0; i<n; ++i){
  22       cin >> t[i];
  23     }
  24     string line;
  25     getline(cin, line);
  26     for (int i=0; i<n; ++i){
  27       getline(cin, line);
  28       stringstream ss(line);
  29       int x, y;
  30       ss >> x;
  31       while (ss >> y){
  32         g[x].push_back(edge(y, (y-x)*t[i], i));
  33         g[y].push_back(edge(x, (y-x)*t[i], i));
  34         x = y;
  35       }
  36     }
  37
  38     int d[100][n];
  39     for (int i=0; i<100; ++i) for (int j=0; j<n; ++j) d[i][j] = INT_MAX;
  40     for (int j=0; j<n; ++j) d[0][j] = 0;
  41
  42     priority_queue<edge> q;
  43     q.push(edge(0, -60, -1));
  44     while (q.size()){
  45       edge top = q.top(); q.pop();
  46
  47       if (top.to == k) break;
  48       if (d[top.to][top.lift] < top.weight) continue;
  49
  50       for (int i=0; i<g[top.to].size(); ++i){
  51         edge u = g[top.to][i];
  52
  53         int t;
  54         if ((t = top.weight + u.weight + (top.lift != u.lift?60:0)) < d[u.to][u.lift]){
  55           d[u.to][u.lift] = t;
  56           q.push(edge(u.to, t, u.lift));
  57         }
  58       }
  59     }
  60     int a = *min_element(d[k], d[k]+n);
  61     if (a < INT_MAX)
  62       cout << a << endl;
  63     else
  64       cout << "IMPOSSIBLE" << endl;
  65
  66
  67   }
  68   return 0;
  69 }